package bin_tree.leetcode;

/**
 * 根据二叉树的前序 + 中序结果还原二叉树
 * @author yuisama
 * @date 2022/02/23 21:10
 **/
public class Num105_BuildTreeByPreAndIn {
    // 当前处理到前序结果集的哪个节点了
    private int index = 0;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeHelper(preorder,inorder,0,preorder.length - 1);
    }

    /**
     * 在preOrder的[left..right]借助中序遍历还原二叉树，返回二叉树的根节点
     * @param preorder
     * @param inorder
     * @param left
     * @param right
     * @return
     */
    private TreeNode buildTreeHelper(int[] preorder, int[] inorder, int left, int right) {
        // 边界
        if (left > right) {
            return null;
        }
        if (index == preorder.length) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[index]);
        index ++;
        int pos = find(root.val,inorder);
        root.left = buildTreeHelper(preorder,inorder,left,pos - 1);
        root.right = buildTreeHelper(preorder,inorder,pos + 1,right);
        return root;
    }

    /**
     * 找到val这个值在中序遍历的索引位置
     * @param val
     * @param inorder
     * @return
     */
    private int find(int val, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == val) {
                return i;
            }
        }
        return -1;
    }
}